<html>
<head><meta charset="utf-8"><title>Implementations of orderedMap · general · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/index.html">general</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Implementations.20of.20orderedMap.html">Implementations of orderedMap</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="200983872"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Implementations%20of%20orderedMap/near/200983872" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Elichai Turkel <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Implementations.20of.20orderedMap.html#200983872">(Jun 16 2020 at 08:04)</a>:</h4>
<p><span class="user-mention" data-user-id="143274">@Amanieu</span> Can hashbrown/SwissTable design support orderedmaps?</p>



<a name="200983913"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Implementations%20of%20orderedMap/near/200983913" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Amanieu <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Implementations.20of.20orderedMap.html#200983913">(Jun 16 2020 at 08:05)</a>:</h4>
<p><a href="https://github.com/bluss/indexmap/pull/131">https://github.com/bluss/indexmap/pull/131</a></p>



<a name="200984460"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Implementations%20of%20orderedMap/near/200984460" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Elichai Turkel <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Implementations.20of.20orderedMap.html#200984460">(Jun 16 2020 at 08:11)</a>:</h4>
<p>That was fast :) Thank You!<br>
<span class="user-mention" data-user-id="138448">@cuviper</span> could you please give a few words on how IndexMap works? (I can't seem to see an explanation)<br>
(ie is it map+vector of keys / pointer to keys? is it something nicer?)<br>
Thanks!</p>



<a name="201054274"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Implementations%20of%20orderedMap/near/201054274" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> cuviper <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Implementations.20of.20orderedMap.html#201054274">(Jun 16 2020 at 18:17)</a>:</h4>
<p><span class="user-mention" data-user-id="249222">@Elichai Turkel</span> yeah, it's basically a hash table containing just indices, referencing the actual items ordered in a vector</p>



<a name="201054310"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Implementations%20of%20orderedMap/near/201054310" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> cuviper <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Implementations.20of.20orderedMap.html#201054310">(Jun 16 2020 at 18:17)</a>:</h4>
<p>so far it's a bespoke table based on robin-hood hashing, but that PR ports it to hashbrown's RawTable</p>



<a name="201054436"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Implementations%20of%20orderedMap/near/201054436" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Elichai Turkel <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Implementations.20of.20orderedMap.html#201054436">(Jun 16 2020 at 18:18)</a>:</h4>
<p>So it's a hashmap containing references as values, and the keys ordered in a vector? (so overhead of N*sizeof(ptr))</p>



<a name="201054438"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Implementations%20of%20orderedMap/near/201054438" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> cuviper <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Implementations.20of.20orderedMap.html#201054438">(Jun 16 2020 at 18:18)</a>:</h4>
<p>so that becomes <code>RawTable&lt;usize&gt;</code>, <code>Vec&lt;Bucket&lt;K, V&gt;&gt;</code>, and the hasher</p>



<a name="201054488"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Implementations%20of%20orderedMap/near/201054488" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> cuviper <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Implementations.20of.20orderedMap.html#201054488">(Jun 16 2020 at 18:18)</a>:</h4>
<p>indexes, not references, but yes</p>



<a name="201054546"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Implementations%20of%20orderedMap/near/201054546" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> cuviper <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Implementations.20of.20orderedMap.html#201054546">(Jun 16 2020 at 18:19)</a>:</h4>
<p>references would have lifetime issues</p>



<a name="201054612"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Implementations%20of%20orderedMap/near/201054612" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Elichai Turkel <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Implementations.20of.20orderedMap.html#201054612">(Jun 16 2020 at 18:19)</a>:</h4>
<p>oh the hashmap contains indexes? hmm, but then any random removal from the hashmap and vec will require iterating through the hashmap and updating the indexes?</p>



<a name="201054777"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Implementations%20of%20orderedMap/near/201054777" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> cuviper <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Implementations.20of.20orderedMap.html#201054777">(Jun 16 2020 at 18:20)</a>:</h4>
<p>removal is painful, yes. indexmap offers <code>swap_remove</code> or <code>shift_remove</code> to pick your poison</p>



<a name="201055011"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Implementations%20of%20orderedMap/near/201055011" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> cuviper <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Implementations.20of.20orderedMap.html#201055011">(Jun 16 2020 at 18:22)</a>:</h4>
<p><span class="user-mention" data-user-id="249222">@Elichai Turkel</span> do you have other ideas how you'd do it?</p>



<a name="201055027"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Implementations%20of%20orderedMap/near/201055027" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Elichai Turkel <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Implementations.20of.20orderedMap.html#201055027">(Jun 16 2020 at 18:22)</a>:</h4>
<p>Hmm I'm trying to find more design patterns for IndexMap, where my use cases are: inserting(always the end of the vec), checking if contains, and removal(random locations in the vec).</p>



<a name="201055114"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Implementations%20of%20orderedMap/near/201055114" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Elichai Turkel <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Implementations.20of.20orderedMap.html#201055114">(Jun 16 2020 at 18:23)</a>:</h4>
<p>My first idea was a vec containing pointers to the keys in the map, or duplicating the key both in the vec and the map(less nice)</p>



<a name="201055370"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Implementations%20of%20orderedMap/near/201055370" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Elichai Turkel <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Implementations.20of.20orderedMap.html#201055370">(Jun 16 2020 at 18:25)</a>:</h4>
<p>another idea is boxing the key, and leaking the pointer storing it both in the map and the vec, and then iterating over the vec to find the pointer itself so you can search in the map, this looses a lot of the nice properties of hashbrown though (cache locality)</p>



<a name="201057009"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Implementations%20of%20orderedMap/near/201057009" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> cuviper <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Implementations.20of.20orderedMap.html#201057009">(Jun 16 2020 at 18:38)</a>:</h4>
<p>tradeoffs abound -- those schemes sound like the table can't help find the index at all</p>



<a name="201057067"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Implementations%20of%20orderedMap/near/201057067" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Elichai Turkel <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Implementations.20of.20orderedMap.html#201057067">(Jun 16 2020 at 18:39)</a>:</h4>
<p>yeah, so in those schemes you need to iterate the vec and compare</p>



<a name="201057164"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Implementations%20of%20orderedMap/near/201057164" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Elichai Turkel <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Implementations.20of.20orderedMap.html#201057164">(Jun 16 2020 at 18:40)</a>:</h4>
<p>idk if this is worse or better than the need to iterate the map and update the indexes for every random removal?</p>



<a name="201057388"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Implementations%20of%20orderedMap/near/201057388" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> cuviper <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Implementations.20of.20orderedMap.html#201057388">(Jun 16 2020 at 18:42)</a>:</h4>
<p>indexmap is definitely weighted toward the assumption that removal is relatively infrequent</p>



<a name="201058093"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Implementations%20of%20orderedMap/near/201058093" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Elichai Turkel <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Implementations.20of.20orderedMap.html#201058093">(Jun 16 2020 at 18:48)</a>:</h4>
<p>I might try to fork it change the design and benchmarks the difference and affects to better understand the exact tradeoffs (I'll wait for the hashbrown PR though before).<br>
I'm currently writing a similar thing in Go, but there I sadly can't get a pointer to the map's key, so I have to duplicate the key itself which sucks.</p>



<a name="201064299"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Implementations%20of%20orderedMap/near/201064299" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> cuviper <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Implementations.20of.20orderedMap.html#201064299">(Jun 16 2020 at 19:42)</a>:</h4>
<p>FWIW, indexmap used to be called ordermap: <a href="https://github.com/bluss/indexmap/issues/14">https://github.com/bluss/indexmap/issues/14</a></p>



<a name="201064351"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Implementations%20of%20orderedMap/near/201064351" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> cuviper <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Implementations.20of.20orderedMap.html#201064351">(Jun 16 2020 at 19:43)</a>:</h4>
<p>if you want to emphasize ordering, and less  indexing, maybe we could offer the old name back to you for your fork</p>



<a name="201064388"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Implementations%20of%20orderedMap/near/201064388" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> cuviper <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Implementations.20of.20orderedMap.html#201064388">(Jun 16 2020 at 19:43)</a>:</h4>
<p>(it's been long enough that hopefully that wouldn't cause confusion)</p>



<a name="201064499"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Implementations%20of%20orderedMap/near/201064499" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> cuviper <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Implementations.20of.20orderedMap.html#201064499">(Jun 16 2020 at 19:44)</a>:</h4>
<p>for example, some folks were suggesting removal by tombstones, which we decided against for indexmap</p>



<a name="201284411"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Implementations%20of%20orderedMap/near/201284411" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Josh Triplett <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Implementations.20of.20orderedMap.html#201284411">(Jun 18 2020 at 15:30)</a>:</h4>
<p>Another option is a table of doubly linked list nodes.</p>



<a name="201284531"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Implementations%20of%20orderedMap/near/201284531" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Josh Triplett <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Implementations.20of.20orderedMap.html#201284531">(Jun 18 2020 at 15:31)</a>:</h4>
<p>More memory usage, and ordered traversal is pointer chasing, but insertion and removal are both constant time.</p>



<a name="201296071"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Implementations%20of%20orderedMap/near/201296071" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Josh Triplett <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Implementations.20of.20orderedMap.html#201296071">(Jun 18 2020 at 16:54)</a>:</h4>
<p>Works better using an intrusive collection, where the pointers live in the objects.</p>



<a name="205238374"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Implementations%20of%20orderedMap/near/205238374" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Elichai Turkel <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Implementations.20of.20orderedMap.html#205238374">(Jul 28 2020 at 13:58)</a>:</h4>
<p><span class="user-mention" data-user-id="120054">@Jon Gjengset</span> Just saw that you forked indexmap, so tagged in-case this discussion might be of interest to you :)</p>



<a name="205239330"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Implementations%20of%20orderedMap/near/205239330" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jon Gjengset <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Implementations.20of.20orderedMap.html#205239330">(Jul 28 2020 at 14:05)</a>:</h4>
<p>Thanks! My use case actually fits the current implementation pretty well, because I only care about the dedicated list of indices to allow me to efficiently choose random keys. This also means that <code>swap_remove</code> is totally fine for me.</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>